2021 Algorithm                       < No.8 이상한 놈>                  Prof. Zoh Q.

2022 Algorithm                     < No.11  마라톤>                     Prof. Zoh Q.

마라톤

[문제]    2022년 부산에서 국제적인 마라톤 대회가 열린다. 우리는 이 대회를 위하여 42.195km의 마라톤 코스를 설계해야 한다. 라마톤 코스 설계를 위한 도시 도로망은 edge에 가중치가 있는 단순 그래프(simple graph) 형식으로 제공된다.  두 교차로 [eqn: x,y]를 연결하는 지나는 도로[eqn: (x,y)]는 모두 정수(km) 길이를 가진 edge이다. 도시의 각 교차로(vertex)는 알파벳 소문자 1자로 표시된다. 따라서 도시는 최대 24개의 정점을 가진 vertex로 표현된다. 우리는 부산대학교 정문에서 출발하여 다시 정문으로 되돌아오는 42km의 순환로를 만들어야 한다. 우리가 완성해야 할 마라톤 코스는 다음의 성질을 만족해야 한다.

42km에서 추가해야할 0.195km는 대회 선수가 경기장 트랙을 뛰도록 하여 이 나머지 거리를 채운다.

1) 출발점  vertex는 항상 스타디움이 위치한 a로 고정되어 있다.

2) 마라톤 코스는 선수들이 헛갈리지 않도록 같은 장소를 재방문하지 않도록 설계되어야 한다. 즉 마라톤 코스에서 출발점을 제외한 모든 점은 서로 달라야 한다.

3) 42km을 이루는 순환로가 하나 이상일 경우에는 가능하면 더 많은 정점을 방문하는 순환로를 더 우선해야 한다. 예를 들면 아래의 예에서 4개의 점([eqn: a rarrow f rarrow l rarrow j rarrow n])을 통과하는 외곽선 42km 순환로보다 파란색으로 표시한 내부 42km의 순환로([eqn: a rarrow b rarrow m rarrow e rarrow k rarrow h rarrow i rarrow d rarrow g])가 더 많은 8개의 지점을 거쳐가므로 이것이 마라톤 코스로 더 선호된다.

선수들이 다양한 지점을 거쳐가도록 해야만 선수들의 피로도 감소되어 더 나은 기록이 만들어질 수 있다.

4) 만일 거쳐 가는 지점의 수도 같으면 경로 정점의 알파벳 리스트(List)의 사전식 순서가 더 빠른 경로를 선호한다. 즉 [eqn: a rarrow b rarrow m....]이나 [eqn: a rarrow g rarrow d rarrow i..] 모두 가능한 마라톤 코스라고 한다면 그 리스트의 알파벳 순서가 빠른 [eqn: a rarrow b rarrow m` LDOTS `]을 우선해야 한다.

5) 어떤 경우 주어진 도시의 도로망에 정확하게 42km의 마라톤 코스가 존재하지 않을 경우도 있다. 이 경우에는 특별히 “None”이라고 답을 해야 한다.

그림-1. 마라톤 대회가 열린 도시 도로망의 예

[입출력]  입력과 출력은 앞서 문제와 같이 표준입출력을 사용한다. 입력 파일의 첫 줄에는 정점(vertex)의 수 [eqn: N]과 edge의 수 [eqn: M]이 주어진다. 이어지는 M개의 각 줄에는 두 정점의 vertex [eqn: u~ v]와 이 둘 간의 거리 [eqn: d_u,v]가 정수로 주어진다. 단 앞에 나오는 정점의 알파벳 순서가 뒤 정점보다 더 빠르다. 따라서 모든 edge (u,v)는 입력 파일에 한번만 나타난다. 그리고 edge의 길이(km)를 나타내는 weight 값의 범위는 [eqn: 1 leq d_u,v `leq 20] 이다. edge가 나타나는 순서는 random하다. vertex는 이름은 항상 연속된 알파벳 순서는 아닐 수 있다. 즉 특정한 vertex는 빠질 수도 있다. 출력으로는 첫 줄에 42km 순환 경로 중에서 앞서 설명한 기준으로 “최적”의 마라톤 코스를 찾아서 그 정점을 수를 먼저 출력한 다음 그 다음 줄에 그 코스를 출력한다. 시작은 정점 a부터 시작하며 마지막 돌아오는 a는 표시하지 않은다.

[예제]

stdin	stdout
14 21 //N, M a f 11 a b 5 d g 2 i j 1 ... (중략) ... e m 6 f l 10 d n 1 a n 10 b c 3 h i 5	9 a b m e k h i d g

[제출조건]  프로그램의 이름은 marathon.{py,cpp, java, c} 로 한다. 이번 과제의 test case별 허용 수행시간은 5초 이며 최대 25번까지 제출 가능하다. 만점자 중에서 전체 수행시간 합으로 가장 빠른 5명과 가장 우아한 코드를 제공한 3명에서 추가 10%의 가점을 주어진다.